package week_five;

public class ReversePairs_493 {

    int ans = 0;

    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return ans;
    }

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end) return;
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        calculate(nums, start, mid, end);
        merge(nums, start, mid, end);
    }

    private void calculate(int[] nums, int start, int mid, int end) {
        int j = mid + 1;
        for (int i = start; i <= mid; i++) {
            while (j <= end && nums[i] > 2L * nums[j]) {
                j++;
            }
            ans += (j - mid - 1);
        }
    }


    private void merge(int[] nums, int start, int mid, int end) {
        int[] help = new int[end - start + 1];
        int l = start, r = mid + 1, i = 0;

        while (l <= mid && r <= end) {
            help[i++] = nums[l] <= nums[r] ? nums[l++] : nums[r++];
        }
        while (l <= mid) {
            help[i++] = nums[l++];
        }
        while (r <= end) {
            help[i++] = nums[r++];
        }
        for (int j = 0; j < help.length; j++) {
            nums[start + j] = help[j];
        }
    }
}
